class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        Set<String> dictionarySet = new HashSet<>();
        for(String root:dictionary) {
            dictionarySet.add(root);
        }
        String[] words = sentence.split(" ");
        for(int i = 0;i < words.length;i++) {
            String word = words[i];
            for (int j = 0; j < word.length(); j++) {
                if (dictionarySet.contains(word.substring(0, 1 + j))) {
                    words[i] = word.substring(0, 1 + j);
                    break;
                }
            }
        }
        return String.join(" ",words);
    }
}